package q719_smallestDistancePair;

import java.util.Arrays;

public class Solution_1 {
    /*
    考虑如何在数对中找出距离第k小的数对
    题目中设定数对必须要(nums[i], nums[j])实际上是不需要考虑的 我们需要求出的是 距离 第k小的数对
    而不是定位它在哪个位置 所以我们可以排序后再求解
    通过排序之后 首先能够确定的是 距离的范围是在 0 - nums[nums.length - 1] - nums[0]之间的
    尽管最小值不一定是0 但是最大值一定是nums[nums.length - 1] - nums[0]
    所以我们在这个区间内进行二分查找 我们每次在这个区间内取出一个 距离
    然后计算 小于这个距离的数对 在数组中有多少个 如果超过了k 代表我们距离取得太小了 而小于k 则距离取得太大

    于是出现第二个问题 如何计算数组中有多少个小于这个距离的数对
    首先我们每次确定一个右边界 j 然后看 从 0 - j之间有多少个数 能够满足 num[j] - nums[i] < mid
    可以转化为nums[i] > nums[j] - mid 于是可以使用二分查找 其实我们可以直观的看
    0 。。。 i
    0 。。。 i 。。。 j
    也就是每次我们需要考虑num[j] - nums[i] 与 mid 如果 num[j] - nums[i] <= mid
    当我们把i取得更小时，显然nums[i]也就越小 因为已排序 所以num[j] - nums[i] 有可能 > mid
    但是i取的更大一定有num[j] - nums[i] <= mid 所以通过不断的二分查找能够找出对于每个j有多少个数对能够满足要求

    最后放回到循环中进行二分查找
     */
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums[nums.length - 1] - nums[0];
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                int i = binarySearch(nums, j, nums[j] - mid);
                count += j - i;
            }

            if (count >= k) {
                r = mid - 1;
            }else {
                l = mid + 1;
            }

        }
        return l;
    }

    private int binarySearch(int[] nums, int end, int target) {
        int l = 0, r = end;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] >= target) {
                r = mid;
            }else {
                l = mid + 1;
            }
        }

        return l;
    }
}
